package com.wkq;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinarySearchTreeNR<E extends Comparable<E>> {
    /**
     * 声明二分搜索树的节点类
     */
    private class Node {
        public E e;
        public Node left;
        public Node right;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    /*根节点*/
    private Node root;
    private int size;

    public BinarySearchTreeNR() {
        this.root = null;
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    //    public void add(E e) {
//        if (root == null) {
//            root = new Node(e);
//            size++;
//            return;
//        }
//        add(root, e);
//    }
//
//    //在以node为根节点的二分搜索树中插入元素e，递归算法
//    private void add(Node node, E e) {
//        if (e.compareTo(node.e) == 0) return;
//        else if (node.e.compareTo(e) > 0 && node.left == null) {
//            node.left = new Node(e);
//            size++;
//            return;
//        } else if (node.e.compareTo(e) < 0 && node.right == null) {
//            node.right = new Node(e);
//            size++;
//            return;
//        }
//        if (node.e.compareTo(e) < 0) add(node.left, e);
//        if (node.e.compareTo(e) > 0) add(node.right, e);
//    }
    public void add(E e) {
        root = add(root, e);
    }

    /*向以node为根的二分搜索树中插入元素e，递归算法；返回插入新节点后二分搜索树的根节点*/
    private Node add(Node node, E e) {
        if (node == null) {//如果递归函数走到了一个node为空的地方，此时就一定要创建一个新的节点
            size++;
            return new Node(e);//return到节点的上层
        }
        if (node.e.compareTo(e) > 0) {
            node.left = add(node.left, e);//因为是可能发生变化的，所以让node.left接住这个变化
        } else if (node.e.compareTo(e) < 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

    //向二分搜索树添加新的元素e，非递归写法
    public void add1(E e) {
        if (root == null) {
            size++;
            root = new Node(e);
            return;
        }
        //用cur来跟踪插入节点的上一个节点
        Node cur = root;
        while (cur != null) {
            if (cur.e.compareTo(e) > 0) {//左
                if (cur.left == null) {
                    cur.left = new Node(e);
                    size++;
                    return;
                } else {
                    cur = cur.left;
                }
            } else if (cur.e.compareTo(e) < 0) {//右
                if (cur.right == null) {
                    cur.right = new Node(e);
                    size++;
                    return;
                } else {
                    cur = cur.right;
                }
            } else {
                return;
            }
        }
    }

    /*二分搜索树中查询元素*/
    public boolean contains(E e) {
        return contains(root, e);
    }

    /*从根节点为node的二分搜索树中查找元素e;递归算法*/
    private boolean contains(Node node, E e) {
        //处理终止情况
        if (node == null) return false;
        if (node.e.compareTo(e) == 0) return true;
        //递归情况
        if (node.e.compareTo(e) < 0) return contains(node.right, e);
        else return contains(node.left, e);
    }

    /*二分搜索树的前序遍历*/
    public void prevOrder() {
        prevOrder(root);
    }

    private void prevOrder(Node node) {
//        if (node == null) return;
        if (node != null) {
            System.out.print(node.e + "    ");

            prevOrder(node.left);
            prevOrder(node.right);
        }
    }

    public void prevOrder2() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.e + "    ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
//        if (node == null) return;
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.e + "    ");
            inOrder(node.right);
        }
    }

    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
//        if (node == null) return;
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.e + "    ");
        }
    }

    public void levelOrder() {
        Queue<Node> queue = new LinkedList<>();
        Queue<Node> res = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node cur = queue.remove();
//            System.out.print(cur + "    ");
            res.add(cur);
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
        System.out.println("queue = " + res);

    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    /*生成以node为根节点，深度为depth的描述二叉树的字符串*/
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if (node != null) {
            res.append(generateDepthString(depth) + node.e + "\r\n");
            generateBSTString(node.left, depth + 1, res);
            generateBSTString(node.right, depth + 1, res);
        }
    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("-");
        }
        return res.toString();
    }


}
